package dp.leetcode_322;

public class DP {
    public int coinChange(int[] coins, int amount) {
        // dp[i] ：凑出金额为 i 所需最少的硬币个数
        int[] dp = new int[amount + 1];
        // 初始化：金额为 0 需要 0 个硬币
        dp[0] = 0;
        // 初始化：将每一种硬币所需最少的硬币个数设置为「无穷大」，表示凑不出该金额的情况
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            // 状态转移方程：dp[i] = Math.min(dp[i - coins[0]] + 1, ..., dp[i - coins[n - 1]] + 1)
            // 金额 i 可能由 i - coins[0] 拼出来, i - coins[1] 拼出来 ... i - coins[n - 1] 拼出来
            // 即拼出 i 元的方案数 = min(拼出 i - coins[0] 的方案数, ..., i - coins[n - 1] 的方案数)
            for (int j = 0; j < coins.length; j++) {
                // 边界处理
                if (i - coins[j] >= 0 && dp[i - coins[j]] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        if (dp[amount] == Integer.MAX_VALUE) {
            dp[amount] = -1;
        }
        return dp[amount];
    }
}
